Zkouška 9.6 – Holan - Pergel

Je dán neorientovaný ohodnocený graf místa s N vrcholy. Ohodnocení hran udává počet vody, kterou spotřebuje karavana při cestě po této hraně

Máme karavanu, která:

• začíná ve vrcholu V,

• má maximální kapacitu vaků s vodou C

• Počáteční stav vody Z

Řekněme, že karavana spotřebuje litr vody na hodinu

Některá místa jsou oázy, kde se doplní vaky s vodou na maximum, těchto oáz je nejvýše O a můžeme je navštívit opakovaně

Je dána množina U míst (k navštívení), které je nutné navštívit v libovolném pořadí. Cílem je najít libovolný časový sled pohybu karavany po grafu (hrany se mohou opakovat), který:

• začíná ve vrcholu V,

• navštíví všechna města ze seznamu S,

• zohledňuje omezení karavany a nutnost doplnění vody.

Není zaručeno, že takový sled existuje.

Vstup

1. Hrany grafu ve tvaru: $[místo1 \ cena \ místo2]$

2. Počáteční informace o karavaně ve tvaru: $[V \ C \ B]$

   • V je název počátečního města

   • C je maximální kapacita vaků s vodou

   • Z je počáteční stav vody

3. Seznam oáz (názvy míst)

4. Seznam míst k navštívení (názvy míst, které je třeba navštívit)

Výstup

Pokud existuje požadovaný sled, vypište jej ve formátu: $[místo \ čas]$

Pro každé místo, které v rámci sledu navštívíme, vypíšeme:

• název města.

• čas příjezdu (např. 00:00, 01:20, atd.),

Čas začíná od 00:00.